#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 二叉树节点
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchlid;
} BiTNode, *BiTree;

// 链式队列节点
typedef struct QNode
{
    BiTree data;
    struct QNode *next;
} QNode;

// 链式队列结构体
typedef struct Queue
{
    QNode *front, *rear;
} Queue;

// 初始化队列
void InitQueue(Queue *q)
{
    q->front = q->rear = (QNode *)malloc(sizeof(QNode));
    q->front->next = NULL;
}

// 判空
bool Empty(Queue *q)
{
    return q->front == q->rear;
}

// 入队
void InQueue(Queue *q, BiTree x)
{
    QNode *p = (QNode *)malloc(sizeof(QNode));
    p->data = x;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

// 出队
bool OutQueue(Queue *q, BiTree *x)
{
    if (Empty(q))
        return false;
    QNode *p = q->front->next;
    *x = p->data;
    q->front->next = p->next;
    if (q->rear == p)
    {
        q->rear = q->front;
    }
    free(p);
    return true;
}

// 初始化一棵树
void InitTree(BiTree &T)
{
    T = NULL;
}

// 插入新节点
void InsertTree(BiTree &T)
{
    int ch;
    scanf("%d", &ch);
    if (ch == -1)
    {
        T = NULL;
    }
    else
    {
        T = (BiTNode *)malloc(sizeof(BiTNode));
        T->data = ch;
        InsertTree(T->lchild);
        InsertTree(T->rchlid);
    }
}
// BiTree createNode(int x)
// {
//     BiTree node = (BiTree)malloc(sizeof(BiTNode));
//     if (!node)
//     {
//         printf("内存分配失败\n");
//         exit(1);
//     }
//     node->data = x;
//     node->lchild = NULL;
//     node->rchlid = NULL;
//     return node;
// }

// 遍历访问
void visit(BiTree T)
{
    printf("%d ", T->data);
}

// 先序遍历
void PreOrder(BiTree T)
{
    if (T)
    {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchlid);
    }
}

// 中序遍历
void InOrder(BiTree T)
{
    if (T)
    {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchlid);
    }
}

// 后序遍历
void PostOrder(BiTree T)
{
    if (T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchlid);
        visit(T);
    }
}

// 层序遍历
void LevelOrder(BiTree T)
{
    if (!T)
        return;
    Queue q;
    InitQueue(&q);
    InQueue(&q, T);
    BiTree p;
    while (!Empty(&q))
    {
        OutQueue(&q, &p);
        visit(p);
        if (p->lchild)
            InQueue(&q, p->lchild);
        if (p->rchlid)
            InQueue(&q, p->rchlid);
    }
}

// 求树的深度
int TreeDepth(BiTree T)
{
    if (!T)
        return 0;
    int l = TreeDepth(T->lchild);
    int r = TreeDepth(T->rchlid);
    // return l > r ? l + 1 : r + 1;
    if (l > r)
    {
        return l + 1;
    }
    else
    {
        return r + 1;
    }
}

int main()
{
    BiTree T;
    InitTree(T);

    printf("请输入节点值，-1 表示空节点（按先序方式输入）:\n");
    // 示例输入：1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1
    // 表示如下结构：
    //         1
    //       /   \
    //      2     3
    //     / \     \
    //    4   5     6

    InsertTree(T);

    printf("先序遍历：");
    PreOrder(T);
    printf("\n");

    printf("中序遍历：");
    InOrder(T);
    printf("\n");

    printf("后序遍历：");
    PostOrder(T);
    printf("\n");

    printf("层序遍历：");
    LevelOrder(T);
    printf("\n");

    printf("树的深度：%d\n", TreeDepth(T));

    return 0;
}